package algorithm;

/**
 * 正向链表反向输出
 */
public class LinkedReverse {


    public static void main(String[] args) {
        //printNode(getNode2());
        //System.out.println();
        //System.out.println("---");
        //reversePrintNode(getNode());

        //reverse2(getNode());
        printNode(reverserByRecursion(getNode()));
    }

    public static void printNode(Node node) {
        if (node != null) {
            System.out.printf("%s\t", node.value);
            printNode(node.next);
        }
    }

    public static void reversePrintNode(Node node) {
        if (node != null) {
            reversePrintNode(node.next);
            System.out.printf("%s\t", node.value);
        }
    }

    public static Node getNode() {
        Node head = null, last = null;
        for (int i = 0; i < 5; i++) {
            Node node = new Node();
            node.setValue(i);
            if (i == 0) {
                head = node;
                last = head;
            } else {
                last.next = node;
                last = node;
            }
        }
        return head;
    }

    public static Node getNode2() {
        Node head = null, last = null;
        for (int i = 0; i < 30; i++) {
            Node node = new Node();
            node.setValue(i);

            if (head == null) {
                head = node;
                last = head;
            } else {
                last.next = node;
                last = node;
            }
        }
        return head;
    }

    /**
     * https://blog.csdn.net/geekmanong/article/details/51097196
     *
     * @param head
     */
    public static void reverse(Node head) {
        if (head == null || head.next == null)
            return;


        Node pre = head;
        Node current = head.next;

        // 原始链表头结点置空,也可以写在最后面，写在此处方便debug看数据
        head.next = null;
        Node next;

        while (current != null) {
            next = current.next;


            current.next = pre;
            pre = current;
            current = next;
        }
        //head.next = null;
        printNode(pre);
    }

    public static void reverse2(Node head) {

        if (head == null || head.next == null) {
            System.out.println("无须反转");
        }

        Node pre = head;

        Node currentDeal = head.next;

        // 原始链表头结点置空,也可以写在最后面，写在此处方便debug看数据
        head.next = null;
        Node next = null;

        while (currentDeal != null) {
            next = currentDeal.next;

            currentDeal.next = pre;
            pre = currentDeal;
            currentDeal = next;
        }

        //head.next = null;

        printNode(pre);
    }

    public static Node reverserByRecursion(Node head) {
        if(head == null || head.next == null){
            return head;
        }

        Node headNode = reverserByRecursion(head.next);

        head.next.next = head;
        head.next = null;

        return headNode;

    }


}

